UnivTrevesV1, Main, Exploration, bibRecord, 000846

Parameterized Measure & Conquer for Problems with No Small Kernels

Identifieur interne : 000846 ( Main/Exploration ); précédent : 000845; suivant : 000847

Parameterized Measure & Conquer for Problems with No Small Kernels

Auteurs : Daniel Binkele-Raible [Allemagne] ; Henning Fernau [Allemagne]

Source :

Algorithmica [ 0178-4617 ] ; 2012.

RBID : Pascal:13-0045947

Descripteurs français

Pascal (Inist)
- Complexité calcul, Paramétrisation, Editeur texte, Algorithmique, Théorie graphe, Analyse algorithme, Recouvrement graphe, Recouvrement ensemble, Ensemble dominant, Arête graphe, ..

English descriptors

KwdEn :
- Algorithm analysis, Algorithmics, Computational complexity, Dominating set, Edge(graph), Graph covering, Graph theory, Parameterization, Set covering, Text editor.

Abstract

Measure & Conquer (M&C) is a prominent technique for analyzing exact algorithms for computationally hard problems, in particular, graph problems. It tries to balance worse and better situations within the algorithm analysis. This has led, e.g., to algorithms for MINIMUM VERTEX COVER with a running time of O(cⁿ) for some constant c ≃ 1.2, where n is the number of vertices in the graph. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to V_ER-TEX COVER, namely CONNECTED VERTEX COVER and EDGE DOMINATING SET. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers. Using M&C in this context will allow us to improve on the hitherto published running times. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000209
to stream PascalFrancis, to step Curation: 000A72
to stream PascalFrancis, to step Checkpoint: 000198
to stream Main, to step Merge: 000866
to stream Main, to step Curation: 000846

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Parameterized Measure & Conquer for Problems with No Small Kernels</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik, Univ. Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Univ. Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik, Univ. Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Univ. Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">13-0045947</idno>
<date when="2012">2012</date>
<idno type="stanalyst">PASCAL 13-0045947 INIST</idno>
<idno type="RBID">Pascal:13-0045947</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000209</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000A72</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000198</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000198</idno>
<idno type="wicri:doubleKey">0178-4617:2012:Binkele Raible D:parameterized:measure:conquer</idno>
<idno type="wicri:Area/Main/Merge">000866</idno>
<idno type="wicri:Area/Main/Curation">000846</idno>
<idno type="wicri:Area/Main/Exploration">000846</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Parameterized Measure & Conquer for Problems with No Small Kernels</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik, Univ. Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Univ. Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB 4-Abteilung Informatik, Univ. Trier</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<wicri:noRegion>Univ. Trier</wicri:noRegion>
<wicri:noRegion>54286 Trier</wicri:noRegion>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Algorithmica</title>
<title level="j" type="abbreviated">Algorithmica</title>
<idno type="ISSN">0178-4617</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Algorithmica</title>
<title level="j" type="abbreviated">Algorithmica</title>
<idno type="ISSN">0178-4617</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Algorithmics</term>
<term>Computational complexity</term>
<term>Dominating set</term>
<term>Edge(graph)</term>
<term>Graph covering</term>
<term>Graph theory</term>
<term>Parameterization</term>
<term>Set covering</term>
<term>Text editor</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Paramétrisation</term>
<term>Editeur texte</term>
<term>Algorithmique</term>
<term>Théorie graphe</term>
<term>Analyse algorithme</term>
<term>Recouvrement graphe</term>
<term>Recouvrement ensemble</term>
<term>Ensemble dominant</term>
<term>Arête graphe</term>
<term>.</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Measure & Conquer (M&C) is a prominent technique for analyzing exact algorithms for computationally hard problems, in particular, graph problems. It tries to balance worse and better situations within the algorithm analysis. This has led, e.g., to algorithms for MINIMUM VERTEX COVER with a running time of O(c<sup>n</sup>
) for some constant c ≃ 1.2, where n is the number of vertices in the graph. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to V<sub>ER</sub>
-TEX COVER, namely CONNECTED VERTEX COVER and EDGE DOMINATING SET. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers. Using M&C in this context will allow us to improve on the hitherto published running times. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
</country>
<region><li>Rhénanie-Palatinat</li>
</region>
<settlement><li>Trèves (Allemagne)</li>
</settlement>
<orgName><li>Université de Trèves</li>
</orgName>
</list>
<tree><country name="Allemagne"><noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
</noRegion>
<name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000846 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000846 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:13-0045947
   |texte=   Parameterized Measure & Conquer for Problems with No Small Kernels
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

Parameterized Measure & Conquer for Problems with No Small Kernels

Parameterized Measure & Conquer for Problems with No Small Kernels

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri